package 算法练习;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月15日 下午8:12:17 
* @Description：
* 
已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。


Tree 1  
     1                            
    / \   
   3   2
  /      
 5          
 
      Tree 2
   2
  / \
 1   3
  \   \
   4   7


合并后的树为
    3
   / \
  4   5
 / \    \
5  4    7



链接：https://www.nowcoder.com/questionTerminal/d7e10a7a25ed4ba59eadeab7b87914b6
来源：牛客网

第一行输入整数n，m。(分别表示树1和树2的节点数,1<=n，m<=100)
接下来n行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第一棵树的第i个结点的左儿子编号，右儿子编号和权值。
接下来m行，第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第二棵树的第i个结点的左儿子编号，右儿子编号和权值。
（对于左右儿子，如果编号为0表示空。保证如果儿子不为空，则儿子编号大于父亲编号。）


输出描述:
输出合并后树按层遍历的各结点权值，相邻权值之间以一个空格相间。
示例1
输入
4 5 
2 3 1
4 0 3
0 0 2
0 0 5
2 3 2
0 4 1
0 5 3
0 0 4
0 0 7
输出
3 4 5 5 4 7
*/
public class 合并二叉树 {

		 public static void main(String[] args){
		        Scanner sc = new Scanner(System.in);
		        int nodeNum1 = sc.nextInt();
		        int nodeNum2 = sc.nextInt();
		         
		        int[] treeArray1 = new int[3 * nodeNum1];
		        int[] treeArray2 = new int[3 * nodeNum2];
		        for (int i = 0; i < treeArray1.length; i++)
		            treeArray1[i] = sc.nextInt();
		        for (int i = 0; i < treeArray2.length; i++)
		            treeArray2[i] = sc.nextInt(); 
		        sc.close();
		         
		        TreeNode t1 = TreeNode.genTree(treeArray1);
		        TreeNode t2 = TreeNode.genTree(treeArray2);
		         
		        TreeNode merge = mergeTree(t1, t2);
		        BFS(merge);
		         
		         
		    }
		     
		    public static TreeNode mergeTree(TreeNode t1, TreeNode t2){
		        if (t1 != null && t2 != null){
		            t1.left = mergeTree(t1.left, t2.left);
		            t1.right = mergeTree(t1.right, t2.right);
		            t1.val += t2.val;
		            return t1;
		        }
		        return t1 == null ? t2 : t1;
		    }
		    //层次遍历
		    public static void BFS(TreeNode root){
		        if (root == null)
		            return;
		        Deque<TreeNode> queue = new ArrayDeque<>();
		        queue.offer(root);
		        int currentSize = queue.size();
		        while (!queue.isEmpty()){
		            while (currentSize-- > 0){
		                root = queue.poll();
		                System.out.print(root.val + " ");
		                if (root.left != null || root.right != null){
		                    if (root.left != null)
		                        queue.offer(root.left);
		                    if (root.right != null)
		                        queue.offer(root.right);
		                }
		                 
		            }
		            currentSize = queue.size();
		        }
		    }
		     
		}
		 
		 
		class TreeNode{
		    TreeNode left;
		    TreeNode right;
		    int val;
		    public TreeNode(int val){
		        this.val = val;
		    }
		    //生成树
		    public static TreeNode genTree(int[] array){
		        Map<Integer, TreeNode> tmp = new HashMap<>();
		        TreeNode root = new TreeNode(0);
		        TreeNode head = root;
		        for (int i = 0, layer = 1; i < array.length; i += 3, layer++){
		             
		            int left = array[i];
		            int right = array[i + 1];
		            int val = array[i + 2];
		             
		            if (tmp.containsKey(layer))
		                root = tmp.get(layer);
		             
		            root.val = val;
		             
		            if (left == 0)
		                root.left = null;
		            else {
		                root.left = new TreeNode(0);
		                tmp.put(left, root.left); //若左子树不为空将编号映射，在对应层数在赋值
		            }
		                 
		            if (right == 0)
		                root.right = null;
		            else {
		                root.right = new TreeNode(0);
		                tmp.put(right, root.right);//若右子树不为空将编号映射，在对应层数在赋值
		            }
		        }
		        return head;
		    }
		}

		 
	
	

